package Offer;

/**
 * 平衡二叉树
 * @author 是阿秋啊
 * @date 2022/04/16 19:10
 **/
public class Num55II {
    public boolean isBalanced(TreeNode root) {
//        if (root == null) {
//            return true;
//        }
//        if (Math.abs(hight(root.left) - hight(root.right)) > 1) {
//            return false;
//        }
//        return isBalanced(root.left) && isBalanced(root.right);
        // 方法一：后序遍历 + 剪枝 （从底至顶）
        return recur(root) != -1;
    }

    private int recur(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = recur(root.left);
        // 如果左子树高度差超过1，则会返回-1
        // 这个if语句起到在函数递归 ，归的时候截断直接返回-1
        if (left == -1) return -1;
        int right = recur(root.right);
        // 此处同上
        if (right == -1) return -1;
        // 如果符合条件则返回大子树高度，不符合返回 -1
        return Math.abs(left - right) < 2 ? Math.max(left,right) + 1 : -1;
    }

    private int hight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(hight(root.left),hight(root.right));
    }
}
